﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include"q.h"


using namespace std;

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//前序遍历(先根遍历) 根结点 左子树 右子树
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL ";
		return;
	}
	//子问题
	cout << (char)root->data << " ";//访问根节点
	PrevOrder(root->left);//访问左子树
	PrevOrder(root->right);//访问右子树
}

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL ";
		return;
	}
	InOrder(root->left);
	cout << (char)root->data << " ";
	InOrder(root->right);
}

//后续遍历
void NextOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL ";
		return;
	}
	NextOrder(root->left);
	NextOrder(root->right);
	cout << (char)root->data << " ";
}

//层序遍历(广度优先遍历) //借助队列先进先出的特点
void TreeLeverOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return;
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		cout << (char)front->data << " ";
		QueuePop(&q);
		if (front->left != NULL)
		{
			QueuePush(&q, front->left);
		}
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
	cout << endl;
}

//销毁一棵树//使用后续销毁
void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;

	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}  

//求二叉树第k层的结点
int TreeKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}

//查找一个结点在不在这棵树?
//BTNode* TreeFind(BTNode* root, BTDataType x)
//{
//	if(root == NULL)
//		return NULL;
//	if (root->data == x)
//		return root;
//	BTNode*node1=TreeFind(root->left, x);
//	if (node1 != NULL)
//		return node1;
//	BTNode*node2=TreeFind(root->right, x);
//	if (node2 != NULL)
//		return node2;
//}

//求二叉树的结点的个数
//1.遍历
void TreeSize1(BTNode* root, int* psize)
{
	//int size = 0;  这样写由于是局部变量，size出函数后就会销毁
	if (root == NULL)
		return;
	else
		(*psize)++;
	TreeSize1(root->left, psize);
	TreeSize1(root->right, psize);
}

//2.分治
int TreeSize2(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		return 1 + TreeSize2(root->left) + TreeSize2(root->right);
}

//求二叉树叶子结点
int TreeLeafSize(BTNode* root)
{
	if (root==NULL)
		return 0;
	if (root->right == NULL && root->left == NULL)
		return 1;
	return TreeLeafSize(root->right) + TreeLeafSize(root->left);
}

//求树的深度
int TreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	/*if (TreeDepth(root->right) > TreeDepth(root->left))
	{
		return TreeDepth(root->right) + 1;
	}
	else 
	{
		return TreeDepth(root->left) + 1;
	}*/

	//上述代码递归返回次数过多，可对上述代码进行修改优化，减少重复的递归返回计算
	int leftDepth = TreeDepth(root->left);
	int rightDepth = TreeDepth(root->right);
	if (leftDepth > rightDepth)
		return leftDepth + 1;
	else
		return rightDepth + 1;
}

//判断一棵树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return true;
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);

	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

//建立一个新的结点
BTNode* CreatNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node != NULL);
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

int main()
{
	BTNode* A = CreatNode('A');
	BTNode* B = CreatNode('B');
	BTNode* C = CreatNode('C');
	BTNode* D = CreatNode('D');
	BTNode* E = CreatNode('E');
	BTNode* F = CreatNode('F');
	BTNode* G = CreatNode('G');


	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	C->left = F;
	C->right= G;

	cout << "前序遍历" << endl;
	PrevOrder(A);

	cout << endl << "中序遍历" << endl;
	InOrder(A);

	cout << endl << "后序遍历" << endl;
	NextOrder(A);

	cout << endl << "层序遍历" << endl;
	TreeLeverOrder(A);

	int sizeA = 0;
	TreeSize1(A, &sizeA);
	cout << endl << "TreeSize1:" << sizeA << endl;

	cout << "TreeSize2:" << TreeSize2(A) << endl;
	cout << "TreeLeafSize:" << TreeLeafSize(A) << endl;
	cout << "TreeDepth:" << TreeDepth(A) << endl;
	cout << "k=3 TreeKsize:" << TreeKSize(A, 3) << endl;
	if (TreeComplete(A) == 1)
		cout << "是完全二叉树" << endl;
	else
		cout << "不是完全二叉树" << endl;
	return 0;
}





//递归
//1.子问题
//2.返回条件（子问题不能再被缩小）

//二叉树
//1.子问题：左子树，右子树
//2.返回条件：空树








//树不能构成环
//满二叉树，k层的树，其节点数为2^k-1。
//完全二叉树，k-1层的结点都是满的，k层的结点从左到右是连续的.
// 
//用数组表示完全二叉树，若父亲的下标为i，则左孩子的下标是2*i-1，有孩子下标是2*i+1
//若孩子的下标是i，则其父亲的下标是（i-1）/2

//二叉树的遍历 前序 中序 后序  层序
//           深度优先遍历    广度优先遍历
//任何一个二叉树都要看成三个部分，根节点，左子树，右子树

//前序（先根遍历）根节点 左子树 右子树